#!/usr/bin/env python

# Implementation by Alex Bendig
# http://www.notjustrandom.com/2009/11/13/finding-frequent-items-in-a-data-stream/

import numpy as np
import operator

class Bucket(object):
        def __init__(self, value = 1, elements = []):
                self.value = value
                self.elements = []

        def __str__(self):
                return "%s: %s" % (self.value, str(self.elements))

        def append(self, element):
                self.elements.append(element)

        def first_element(self):
                if self.elements:
                        return self.elements[0]
                else:
                        return None

        def has_elements(self):
                return len(self.elements) > 0

        def remove(self, element):
                self.elements.remove(element)

class StreamSummary(object):
        """
        Maintains a dictionary of elements and a list of buckets. Each element
        points to a (parent) bucket.
        The bucket list is sorted based on the buckets' values. Each bucket also
        maintains a list of elments.
        This has the effect of grouping elements with equal values in buckets.
        """
        def __init__(self):
                self.elements = {}
                self.buckets = []

        def __len__(self):
                return len(self.elements.keys())

        def __str__(self):
                result = ""
                for b in self.buckets:
                        result += str(b) + " "
                return result

        def add_element(self, element):
                """
                Adds an element and ensures it's assigned to the correct bucket.
                """
                if not self.elements.has_key(element):
                        if not self.buckets or self.buckets[0].value != 1:
                                self.buckets.insert(0, Bucket())
                        self.elements[element] = self.buckets[0]
                        self.buckets[0].elements.append(element)

        def increase_element(self, element):
                """
                Increasing an element's value also means assigning it to the
                correct bucket. That can result in creating a new bucket and/or
                removing an empty one.
                """
                current_bucket = self.elements[element]
                bucket_index = self.buckets.index(current_bucket)

                if len(self.buckets) == bucket_index + 1:  # last bucket
                        self.buckets.append(Bucket(value = current_bucket.value + 1)) # create new bucket
                elif self.buckets[bucket_index + 1].value > current_bucket.value + 1: # insert new bucket between current and next
                        self.buckets.insert(bucket_index + 1,
                                            Bucket(value = current_bucket.value + 1))
                current_bucket.remove(element)
                self.elements[element] = self.buckets[bucket_index + 1]
                if not current_bucket.has_elements():
                        del self.buckets[bucket_index]
                self.elements[element].append(element)

        def has_element(self, element):
                return self.elements.has_key(element)

        def get_minimum(self):
                if self.buckets:
                        #print (self.buckets[0].first_element()==None)
                        return self.buckets[0].first_element()
                else:
                        #print "self.buckets[0] == None"
                        return None

        def replace_element(self, old_element, new_element):
                """
                Replaces an existing element with an entirely new element in
                the old element's bucket.
                """
                self.elements[new_element] = self.elements[old_element]
                self.elements[new_element].remove(old_element)
                self.elements[new_element].append(new_element)
                del self.elements[old_element]

def space_saving_frequent_k(k, stream):
        summary = StreamSummary()
        for element in stream:
                #print "inserting ", element
                #print summary
                if summary.has_element(element):
                        #print "already monitored"
                        summary.increase_element(element)
                elif len(summary) < k:
                        #print "!monitored. < k"
                        summary.add_element(element)
                else:
                        current_minimum_key = summary.get_minimum()
                        #print (current_minimum_key)
                        if current_minimum_key:

                                #print "!monitored. >k. Min exists: "
                                summary.replace_element(current_minimum_key, element)
                                summary.increase_element(element)
                        else:
                                #print "!monitored. > k. Min not exists"
                                summary.add_element(element)
                #print "end of INsert"
        return summary

#_stream = np.random.zipf(2., 100)
_stream = []
#_stream = np.random.zipf(2.8, 100000)
file = open('zipf.out', 'r')

for i in file.readlines() :
    _stream.append(int(i.strip()));

_summary = space_saving_frequent_k(5, _stream)
exact = {}
for item in _stream :
    if item not in exact :
        exact[item] = 1
    else :
        exact[item] += 1

#exact_sorted = OrderedDict(sorted(exact.items, key=lambda exact: exact[1] ) )
#for key in sorted(exact, key=operator.itemgetter(1), reverse=True) :
#    exact_sorted.append((key, exact[key]))
exact_sorted = sorted(exact.items(), key=lambda(k,v):(v,k), reverse=True)

#for item in _summary.elements :
#    #print (item)
    #item.value = list(item.value)
    #item.value.append(exact[item])
print (_summary)
print len(_summary)
print len(_summary.buckets)


for item in exact_sorted[:10] :
    print (item)